package hot;

public class Num96 {
    //卡塔兰数
    //G(n) :n个值可以组成多少个二分搜索树
    //F(i,n):以i为根，长度为n的数组可以组成多少个二分搜索树
    //F(i,n) = G(i - 1) * G(n - i)
    //              i=1
    //G(n) = G(n)=   ∑ F(i,n)
    //               n
    //G(n) = 2 * G(n - 1) * (2 * i + 1) /  (i + 2);
    public int numTrees(int n) {
        long G = 1;
        for(int i = 1; i < n; i++) {
            G = 2 * G * (2 * i + 1) /  (i + 2);
        }
        return (int)G;
    }
}
